package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/generate-parentheses/
 *
 * @author tzp
 * @since 2020/10/16
 */
public class LC22 implements Backtracking {
    List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        backtracking(n * 2, 0, 0, new StringBuilder());
        return result;
    }

    public void backtracking(int remainLength, int zuoNum, int youNum, StringBuilder path) {
        if (remainLength == 0) {//终止回溯
            result.add(path.toString());
        } else {
            if (zuoNum == youNum) {//只能选左括号
                path.append('(');
                backtracking(remainLength - 1, zuoNum + 1, youNum, path);
                path.deleteCharAt(path.length() - 1);
            } else if (zuoNum - youNum == remainLength) {//剩下的都放右括号, 提前终止
                char[] a = new char[zuoNum - youNum];
                Arrays.fill(a, ')');
                result.add(path.toString() + new String(a));
            } else if (zuoNum > youNum) {//左>有
                path.append('(');
                backtracking(remainLength - 1, zuoNum + 1, youNum, path);
                path.deleteCharAt(path.length() - 1);
                path.append(')');
                backtracking(remainLength - 1, zuoNum, youNum + 1, path);
                path.deleteCharAt(path.length() - 1);
            } else {
                throw new RuntimeException();
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC22().generateParenthesis(3));
        System.out.println(new LC22().generateParenthesis(1));
        Integer cur = (int) '2';
        System.out.println(cur);
    }
}
